package org.leetcode1000.LCR;

import org.jikeshijian.Solution;

/**
 * @Auther: qingle
 * @Date: 2024/10/8-4:23
 * @Description:
 * @version: 1.0
 */
public class LCR_121_二维数组目标值 {

	/**
	 * 每一行从左到右递增，每一列从上到下递增，符合二分查找的规律
	 */
	public boolean findTargetIn2DPlants(int[][] matrix, int target) {

		// 1.行和列,边界值
		 if (matrix.length == 0 || matrix[0].length == 0)
		     return false;
		int rows = matrix.length;
		int cols = matrix[0].length;
		int low = 0, high = rows * cols - 1;

		int i;
		for (i = 0; i < rows; i++) {
			while (low <= high) {
				int mid = low + (high - low) / 2;
				if (target == matrix[i][mid]) {
					return true;
				} else if (target < matrix[i][mid]) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}
		}
		return false;
	}


	public static void main(String[] args) {
		LCR_121_二维数组目标值 solution = new LCR_121_二维数组目标值();

		// 示例 1
		int[][] plants1 = {{2,3,6,8},{4,5,8,9},{5,9,10,12}};
		int target1 = 8;
		boolean result1 = solution.findTargetIn2DPlants(plants1, target1);
		System.out.println("示例 1 结果: " + result1); // 应该输出 true

		// 示例 2
		int[][] plants2 = {{1,3,5},{2,5,7}};
		int target2 = 4;
		boolean result2 = solution.findTargetIn2DPlants(plants2, target2);
		System.out.println("示例 2 结果: " + result2); // 应该输出 false
	}
}
